package cuiyt.offer;

/**
 * @author cyt
 * @create 2020-05-26 16:52
 */
public class T29 {

    /**
     * 中序遍历
     * [3,2,8,4,9,1,6,5,7]
     * 先序遍历
     * [1,2,3,4,8,9,5,6,7]
     * 1
     * 2     5
     * 3  4  6 7
     * 8 9
     *
     * @param args
     */
    public static void main(String[] args) {


    }

    static TreeLinkNode findAns(TreeLinkNode pNode) {

        // 判断 右子树是否 为空

        if (pNode.right != null) {
            TreeLinkNode node = pNode.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        } else {
/*                            1
                        2     5
                       3  4  6 7
                         8 9

 [3,2,8,4,9,1,6,5,7]
                         */

            while (pNode.next != null) {
                TreeLinkNode patent = pNode.next;
                if (patent.left == pNode) {
                    return patent;
                }
                pNode = pNode.next;
            }
        }
        return null;

    }
}

class TreeLinkNode {

    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
